#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#include<unordered_set>
#define MOD 1000000007
class Solution {
public:
    int nthUglyNumber(int n) {
        std::vector<int> arr(n+1,0);
        arr[1]=1;
        for (int i=2,t2 = 1,th=1,f=1;i<=n;i++)
        {
            int a = arr[t2]*2;
            int b = arr[th]*3;
            int c = arr[f]*5;

            int j = t2;
            int min= 0;
            if (a<b)
            {
                j=t2;
                min = a;
            }else
            {
                j=th;
                min = b;
            }

            if (c<min)
            {
                min = c;
                j = f;
            }
            arr[i] = min;
            if (min == a) t2++;
            if (min==b) th++;
            if (min==c) f++;
        }
        return arr[n];
        
    }
};
